# 给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
#
#  示例 1 ：
# 输入：num = "1432219", k = 3
# 输出："1219"
# 解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
#
#  示例 2 ：
# 输入：num = "10200", k = 1
# 输出："200"
# 解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
#
#  示例 3 ：
# 输入：num = "10", k = 2
# 输出："0"
# 解释：从原数字移除所有的数字，剩余为空就是 0 。
class Solution:
    def removeKdigits2(self, num: str, k: int) -> str:
        """
         贪心 + 单调栈
         对于两个相同长度的数字序列，最左边不同的数字决定了这两个数字的大小，因此若要使得剩下的数字最小，需要保证靠前的数字尽可能小

         贪心策略：
         给定一个长度为 n 的数字序列 [D0,D1,D2,D3,…Dn−1]，从左往右找到第一个位置 i（i>0）使得 D(i)<D(i−1)，并删去 D(i−1)；
         如果不存在，说明整个数字序列单调不降，删去最后一个数字即可。
         使用单调递增栈进行优化
         考虑从左往右增量的构造最后的答案。我们可以用一个栈维护当前的答案序列，栈中的元素代表截止到当前位置，删除不超过 k 个数字后，所能得到的最小整数。

         :param num:
         :param k:
         :return:
         """
        stack = []
        for n in num:  # 构建单调递增的数字串
            while stack and k > 0 and stack[-1] > n:
                stack.pop()
                k -= 1
            stack.append(n)
        stack = stack[:-k] if k > 0 else stack  # K > 0，还要删除末尾的 K 个字符
        return ''.join(stack).lstrip('0') or '0'  # 去掉前导'0'，返回

    def removeKdigits1(self, num: str, k: int) -> str:
        """
        解法一:暴力法(贪心策略)
        若要使得剩下的数字最小，需要保证靠前的数字尽可能小。

        从左往右找到第一个位置 i（i>0）使得 num[i]<num[i-1]并删去 str[i−1]
        如果不存在，说明整个数字序列单调不降，删去最后一个数字即可。
        重复k次即可
        :param num:
        :param k:
        :return:
        """
        numList = list(num)

        def remove() -> None:
            for index in range(1, len(numList)):
                if numList[index] < numList[index - 1]:
                    del numList[index - 1]
                    return
            del numList[-1]

        for i in range(k):
            remove()

        while len(numList) >= 1 and numList[0] == "0":  # 重复k次后去掉前导'0'
            del numList[0]
        return ''.join(numList) if numList else '0'

    def removeKdigits(self, num: str, k: int) -> str:
        return self.removeKdigits2(num, k)


if __name__ == "__main__":
    num = "1432219"
    k = 3
    # num = '10'
    # k = 2
    num = '10200'
    k = 2
    print(Solution().removeKdigits(num, k))
